package features.advance.leetcode.tree.easy;

import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

/**
 *
 * 111. 二叉树的最小深度
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明：叶子节点是指没有子节点的节点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：2
 * 示例 2：
 *
 * 输入：root = [2,null,3,null,4,null,5,null,6]
 * 输出：5
 *
 *
 * 提示：
 *
 * 树中节点数的范围在 [0, 105] 内
 * -1000 <= Node.val <= 1000
 *
 *
 * @author LIN
 * @date 2021-04-28
 */
public class Solution111 {

    public int minDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        int min_depth = Integer.MAX_VALUE;

        if(root.left != null){
            min_depth = Math.min(minDepth(root.left),min_depth);
        }
        if(root.right != null){
            min_depth = Math.min(minDepth(root.right),min_depth);
        }
        return min_depth + 1;
    }


    public static void main(String[] args) {

        String str = "[3,null,20,null,2,null,7,null]";
        TreeNode treeNode = TreeUtil.parseArray(str);
        Solution111 solution111 = new Solution111() {
        };
        int i = solution111.minDepth(treeNode);
        System.out.println(i);
    }
}
